package cn.zifangsky.array.questions;

import org.junit.Test;

/**
 * 寻找旋转排序数组中的最小值
 *
 * <p>假设一个排好序的数组在其某一未知点发生了旋转（比如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2 ）。你需要找到其中最小的元素。</p>
 *
 * <ol>
 *     <li>输入：[4, 5, 6, 7, 0, 1, 2]；结果：0</li>
 *     <li>输入：[3, 4, 5, 1, 2]；结果：1</li>
 *     <li>输入：[3, 1, 2]；结果：1</li>
 * </ol>
 *
 * @author zifangsky
 * @date 2020/10/20
 * @since 1.0.0
 */
public class Problem_006_FindTheSmallestValueInARotatedSortedArray {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        int[] arr1 = new int[]{4, 5, 6, 7, 0, 1, 2};
        int[] arr2 = new int[]{3, 4, 5, 1, 2};
        int[] arr3 = new int[]{3, 1, 2};
        int[] arr4 = new int[]{2, 3, 4, 5, 1};

        //结果：0
        System.out.println("方法一：" + this.findMin1(arr1) + "，方法二：" + this.findMin2(arr1));
        //结果：1
        System.out.println("方法一：" + this.findMin1(arr2) + "，方法二：" + this.findMin2(arr2));
        //结果：1
        System.out.println("方法一：" + this.findMin1(arr3) + "，方法二：" + this.findMin2(arr3));
        //结果：1
        System.out.println("方法一：" + this.findMin1(arr4) + "，方法二：" + this.findMin2(arr4));
    }

    /**
     * 方法一（暴力破解）：直接单次循环遍历搜索整个数组找到最小元素，时间复杂度为 O(n)。
     */
    private int findMin1(int[] nums) {
        if(nums == null || nums.length < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        int min = Integer.MAX_VALUE;
        for(int num : nums){
            if(num < min){
                min = num;
            }
        }

        return min;
    }

    /**
     * 方法二（改进的二分查找，时间复杂度为O(log(n))）：
     * <ol>
     *     <li>如果 nums[left] <= nums[right]，则说明 nums 是有序数组，直接返回 nums[left] 即可</li>
     *     <li>如果 nums[left] < nums[mid]，则说明 nums[left, mid] 是有序数组，最小值在 nums(mid, right] 之间，令 left=mid+1</li>
     *     <li>如果 nums[left] > nums[mid]，则说明 nums[mid, right] 是有序数组，最小值在 nums[left, mid] 之间，令 right=mid</li>
     * </ol>
     */
    private int findMin2(int[] nums) {
        if(nums == null || nums.length < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        int left = 0, right = nums.length - 1;
        while (left < right){
            //1. 最小值在left
            if(nums[left] <= nums[right]){
                return nums[left];
            }

            int mid = (right + left) / 2;
            //2. 最小值在(mid, right]
            if(nums[left] <= nums[mid]){
                left = mid + 1;
            }
            //3. 最小值在[left, mid]
            else{
                right = mid;
            }
        }

        return nums[left];
    }

}
